# 树的结点
class Node:
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


# 树的方法
class Tree:
    def __init__(self):
        self.root = None  # 树的根节点
        self.help_queue = []  # 辅助队列，用列表来代替，help_queue[0]是队列头,列表尾就是队尾

    def create_tree(self, node: Node):
        self.help_queue.append(node)
        if self.root is None:
            self.root = node
        else:
            if self.help_queue[0].lchild is None:
                self.help_queue[0].lchild = node
            else:
                self.help_queue[0].rchild = node
                self.help_queue.pop(0)

    def pre_order(self, node: Node):
        if node is None:
            return
        print(node.elem, end=" ")
        self.pre_order(node.lchild)
        self.pre_order(node.rchild)

    def mid_order(self, node: Node):
        if node:
            self.mid_order(node.lchild)
            print(node.elem, end=" ")
            self.mid_order(node.rchild)

    def post_order(self, node: Node):
        if node is None:
            return
        self.post_order(node.lchild)
        self.post_order(node.rchild)
        print(node.elem, end=" ")

    def level_order(self, node: Node):
        help_queue = []
        help_queue.append(node)
        while help_queue:
            out_node = help_queue.pop(0)
            print(out_node.elem, end=" ")
            if out_node.lchild:
                help_queue.append(out_node.lchild)
            if out_node.rchild:
                help_queue.append(out_node.rchild)


if __name__ == '__main__':
    tree = Tree()
    for i in range(1, 11):
        node = Node(i)
        tree.create_tree(node)

    tree.pre_order(tree.root)
    print()
    tree.mid_order(tree.root)
    print()
    tree.post_order(tree.root)
    print()
    tree.level_order(tree.root)